This invention relates to block cipher secret-key cryptographic systems and methods. More particularly, the invention relates to improvements in a secret-key cryptographic system and method which uses data-dependent and variable rotations of data in block cipher rounds which are dependent, directly or indirectly, on plain text data being enciphered.
Cryptography is the science of securing communications and information. In recent years, the importance of cryptographic systems has been magnified by the explosive growth and deployment of telecommunications technology. Increasing volumes of confidential data are being transmitted across telecommunications channels and are being stored in file servers, where such data ranges from financial information to electronic votes. It is desired that systems provide security from unsanctioned or illicit interception or modification of such confidential information.
There are two basic operations used in secret-key or symmetric block cipher cryptography. Encryption or encipherment is the process of disguising a communication to hide its content. During encryption, the communication which is known as plaintext is encrypted into what is known as ciphertext. Decryption or decipherment is the inverse process of using the same secret-key values to recover the plaintext from the ciphertext output. While the two basic operations of encryption and decryption may be distinguished in practice, there is in general no necessary mathematical difference between the two operations, other than that they are inverse transformations of each other.
Ciphertext output of a secure block cipher has little or no statistical relation to its corresponding plaintext input. The output (or input) is uncorrelated to the input (or output). Every bit of ciphertext output reflects every bit of the plaintext input and every bit of the key in a complex uncorrelated manner, just as every bit of recovered plaintext input reflects every bit of the ciphertext output and every bit of the key in a complex uncorrelated manner.
Block ciphers, generally, are binary ciphers receiving inputs consisting of a fixed number of bits (a block of n-bits), and have outputs of the same fixed number of bits (an equal sized block of n-bits). The input and output of such ciphers are one-to-one mappings: each ordered n-bit input is transformed by the block cipher into only one ordered n-bit output; and further, when the transformation is computed in reverse each ordered n-bit output may be transformed back into only one ordered n-bit input.
Secret key values are the values which influence the mapping of input to output provided by the block cipher. It is useful to divide secret keys into two categories: secret input keys and secret keys. Secret input keys may be based on varied input from a user or the encryption system which may be of fixed or variable length, and a secret key is often a transformed secret key input. A secret key is usually of fixed length. A block cipher usually operates on a secret key, but in some cases may operate on an secret input key. If a block cipher first operates on a secret input key, potentially it may use some algorithm to transform the secret input key into a secret key in a standard format. Then, a block cipher expands the secret key to form subkeys whose length or number of bits exceeds that of the secret key.
Block ciphers and have many rounds calculated in series where each round depends on plaintext through the output of the immediately prior round where generally in each round the same operations are performed iteratively in the same manner. The n-bit input into the block cipher may be called n-bit cipher input. After encryption, the result may be called n-bit cipher output. In each of these rounds, the ordered binary input may be called n-bit cipher round input, and the n-bit ordered binary output may be called n-bit cipher round output. An n-bit cipher input or n-bit cipher output refers to the variable n-bit binary input or variable n-bit binary output of a binary block cipher. Such n-bit cipher input and n-bit cipher output are typically plaintext input and ciphertext output. By contrast, key inputs or subkey values used by a binary block cipher are not variable binary inputs, but are generally fixed or predetermined values for a given use of the block cipher. An n-bit cipher round input or n-bit cipher round output refers to the variable n-bit binary input or variable n-bit binary output of one (and typically of one operative round) round of a binary block cipher.
An operative round of a binary block cipher is an iterative round which calculates new values for each of x primary segments in the round, where x may vary in different operative rounds, where there are a total of n-bits in the x primary segments, and where the new values of the x primary segments determine the n-bit round output. Operative rounds of a binary block cipher refer to iterative rounds which calculate new values for each of x primary segments in a given round, where x may vary in different rounds, where the n-bit cipher round output consists of these x segments of new values, and where the total of all bits of the x segments equals n bits. Binary block ciphers are ciphers receiving inputs consisting of n ordered bits of input and have outputs of the same number of ordered bits (n bits). A mapping of block cipher inputs to outputs reveals that every possible combination of n input bits from 2{circumflex over ( )}n possible combinations has only one corresponding combination of n output bits, and likewise every combination of n output bits from 2{circumflex over ( )}n possible combinations has only one corresponding combination of n input bits. In other words, binary block ciphers transform input values to output values in a manner such that the mapping of this transformation relates the members of the set of all possible ordered input values of n-bits in a one-to-one manner with the members of the set of all possible ordered output values of n-bits.
While a segment is defined simply as a plurality of ordered bits, it is also possible to classify types of segments. There are also round segments and one-to-one round segments.
A round segment is a segment within a round (and typically an operative round) of a binary block cipher which is part of n-bit cipher input or n-bit cipher output, or is calculated within a round or operative round the operative round and is intermediate between input and output; is affected by n-bit cipher round input; and affects n-bit cipher round output. For example, a first value in a calculation is said to affect a second value if, after taking into account the specifics of the particular calculation, a random change in all bits of the first value is likely to change at least one bit of the second value with a chance of at least one in three.
A one-to-one round segment is defined as a member of a one-to-one round segment set. A one-to-one round segment set is defined as a set of ordered round segments in an operative round of a binary block cipher where it is true that each n-bit round input corresponds with only one possible result or group of particular values of the ordered segments of that set, and that any group of particular values of the ordered segments of that set correspond with only one possible n-bit round input. For example, the set of segments in the n-bit cipher output are a one-to-one round segment set. The set of segments in any of the n-bit round input or the n-bit round output of each operative round are also one-to-one round segment sets. Where one-to-one round segment sets are calculated in a binary block cipher which operates on n-bits of input or output, it obviously follows that all such one-to-one round segment sets consist of exactly n-bits.
Note that in general there are usually more one-to-one round segment sets than the examples just mentioned. For example, in most binary block ciphers it is possible to form one-to-one round segment sets by combining particular round segments which are determined consecutively even though they are determined in different rounds.
There is a term-of-art in which one speaks of the n-bit data or bits (which for block ciphers can be called text or plaintext or cipher data) of a calculation method from encryption. Such data is generally dependent on any variable input into the method from plaintext. If so, such data is, in another term-of-art, also called variable as opposed to predetermined or fixed. Consequently, one can speak of all the n-bit data (all the bits) in one-to-one round segment sets as being variable; and such data is different than the predetermined secret subkey data which is also part of block ciphers. Such subkey data is dependent on the secret key, and is fixed and often precalculated relative to any variable plaintext input of the block cipher.
One can observe further that in a well designed block cipher most bits of variable round segments are variable. This observation is true for efficient block ciphers since any non-variable bits can be wasteful or inefficient. For example, although a round segment may be called variable as it has at least one variable bit within it by definition, in a well designed block cipher if a round segment is variable in general, a substantial portion (such as 50 out of 64) of the bits within that round segment will also be variable.
Further, block ciphers may linearly combine one-to-one round segments with subkeys, or rotate them by a predetermined number of bits, or rotate them by a data-dependent number of bits determined by some bits of another unrelated one-to-one round segment, or even combine them linearly with other unrelated one-to-one round segments, and generally such resulting output segments, which are sometimes intermediate values that do not affect n-bit output directly, are also one-to-one round segments.
Finally, the preceding description of primary segment values while sufficient for understanding the scope of the prior art is incomplete. Typically, primary segment values are more than just calculated round segment values which determine a n-bit round output. Typically, a n-bit round input contains old or prior values of primary segments which are replaced over the course of an operative round. Typically, each such replacement value of a primary segment is a one-to-one function of the prior value, if all subkey values and all other primary segments are constant. Generally, all primary segment values are one-to-one round segments.
To increase security each operative round typically interacts one-to-one round segments and secret subkey values. In each operative round, each of the x primary segments is typically a function of its prior segment modified by the combined interaction of at least one other one-to-one round segment and in some cases by a subkey segment for that round.
In practice, execution of block ciphers in microprocessors generally takes place using registers, which typically are the data locations in a microprocessor which are quickest at loading and storing data. Often, binary block ciphers are configured such that the usual segment operated on by the rounds of the block cipher is equal in size to the 32-bit or 64-bit registers of microprocessors which may compute the block cipher.
Increasingly, not only do binary block ciphers use algorithms optimized for 32-bit or 64-bit registers but also they use algorithms which are optimized for the microprocessors of network servers, which are typically internet or intranet nodes. Such network nodes usually must be capable of more than just encryption or decryption. In fact, the majority of time and resources of such servers is allocated to other tasks. As a result, it is critical that a block cipher well suited to this task be capable of quick bootup or startup and make minimal use of on-chip cache, which is one of the most critical resources of a server""s microprocessor.
Another type of encryption which may not require as much optimization as node encryption on network servers is bulk encryption of large files. Calculation of block ciphers, well suited to bulk encryption, typically takes place in registers. However, as the amount of data to be encrypted is larger in bulk encryption, quick startup is not essential. Such startup time becomes a small percentage of the total time spent encrypting a large file.
A good example of perhaps the first historically significant symmetric cryptographic system (i.e., when the same key is used in the encipherment and decipherment transformations) is the Data Encryption Standard (xe2x80x9cDESxe2x80x9d), which is a U.S. Government standard. DES uses small xe2x80x9cs-boxesxe2x80x9d to provide security. These so-called s-boxes are substitution boxes or, simply, look-up tables.
S-boxes provide output which is a nonlinear function of the input, based on a lookup table. Small s-boxes are lookup tables with a small number of possible inputs. Often, small s-boxes have a small number of output bits as well. For example, each s-box of DES has 6-bit inputs or 64 possible inputs and 4-bit outputs or 16 possible output values. They do not require much memory; nor does it take long to load them in microprocessor memory. S-boxes are generally stored in on-chip cache, generally the next quickest form of microprocessor memory after registers.
DES was the first significant example of a Feistel block cipher. Such block ciphers are named after Horst Feistel. Feistel block ciphers perform repetitive operations on a left half and right half of a block, respectively. This is convenient for execution in hardware and software when the number of registers is limited.
One aspect of DES which is particularly relevant to the defined terms used herein is the fact it swaps its primary segments, also known in DES as cipher block halves. If the swaps are included, some equations which describe in a general way both segments being recalculated in each two successive iterative rounds, are as follows, where LH means the left half, and RH means the right half:
increment i by +1 
LH=LH xor F(RH xor Key[i]) 
Swap{LH,RH}
increment i by +1 
LH=LH xor F(RH xor Key[i]) 
Swap{LH,RH}xe2x80x83xe2x80x83Eq. 1 
This sequence of calculation is mathematically equivalent to the simpler equations and the operative round below:
increment i by +2 
LH=LH xor F(RH xor Key[i]) 
RH=RH xor F(LH xor Key[i+1])xe2x80x83xe2x80x83Eq. 2 
The approach used herein is to discuss ciphers and their round equations in general using terms developed for those particular ciphers which are expressed without any obscuring primary segment swaps or other similar operators which might have a similar effect, in order to focus on the internal mathematical structure and logic of each round of each cipher. This discussion while simplified is meant to apply also to all ciphers even if they are expressed in a complicated manner using such primary segment swaps or other obscuring operators.
What is relevant about the above simplified presentation of DES is that each such operative round calculates two new values of the primary segments which are part of a n-bit round output. Further, DES applies its nonlinear function to each of the primary segments LH and RH which are part of a n-bit round output. This general structure of DES in which all functions are applied to each of the primary segments is copied in almost all other block ciphers.
Another common feature of most efficient implementations of DES which is copied elsewhere is to place each block half or primary segment in the register of a microprocessor. This feature allows certain desired cryptographic operations to be performed quickly. For example, it becomes possible to add a block half with a subkey, or to xor block halves together, in only one operation (typically in one microprocessor clock cycle). As is well known, xor indicates bitwise exclusive-or. It is an operator which interacts bits in identical positions. If Z equals X xor Y, the result of each bit in a given position in Z equals the exclusive-or of the two bits in the same positions in X and Y.
Unfortunately, small s-boxes generally do not permit ciphers that are efficient, i.e., both fast and secure. Larger s-boxes are typically consistent with more efficient block ciphers. However, large s-boxes either use a significant percentage of on-chip cache (competing with other desired uses of on-chip cache), or they must be loaded prior to each use (which is time consuming). While use of larger s-boxes might increase the efficiency and speed of DES, it would also increase startup time and the use of on-chip cache.
Two interesting examples of Feistel block ciphers which use large s-boxes are the two ciphers referred to as Khufu and Khafre, see, e.g., U.S. Pat. No. 5,003,597. These block ciphers use s-boxes where the 8-bit inputs are considerably smaller than their 32-bit outputs. This approach is consistent with the fact that modern microprocessors take an equal number of clock cycles to compute s-boxes with 32-bit output as they do s-boxes with 8-bit output. So while the output size of the s-box increases, so too does the strength and efficiency of the cipher given a constant number or rounds or clock cycles. Khufu and Khafre are both Feistel block ciphers having many varied details which are not directly relevant here.
In general, Khufu and Khafre ciphers have the following structural characteristics:
First, similar to other Feistel block ciphers, it is convenient to compute the ciphers using two registers which contain the bit-values of the left and right halves. In each round of the block cipher, each register of cipher data is recalculated. This process updates and modifies the initial value of each register, which is the old primary segment, and substitutes a new register value, which is a new primary segment. In this approach, each new primary segment is mapped one-to-one with its old primary segment, all subkey segments and other primary segments being equal.
Second, each new primary segment reflects not only the corresponding old primary segment but also a small number of bits which are the least significant bits (xe2x80x9clsbxe2x80x9d) of the other register. The lsb affect the new one-to-one round segment in a non-linear manner using s-boxes. The s-boxes of Khufu and Khafre have 8-bit inputs and 32-bit outputs. They accept 8-bit inputs from the last calculated register, and their 32-bit outputs affect the new primary segment in the register currently being computed.
Khufu and Khafre ciphers are unlike most other Feistel block ciphers in that there is only one non-linear operation (i.e., an s-box operation) in each round; it accepts input from only a small fraction or small section of the one-to-one round segment (8 bits), and that non-linear operator potentially affects all the bits of the other one-to-one round segment. This small section is generally less than thirty-five percent of the one-to-one segment which contains the small section. This process of using in each round a small section of a recently calculated one-to-one round segment to affect the new one-to-one round segment in a non-linear manner may be called bit expansion of a small section.
Third and finally, Khufu and Khafre use rotation as an efficient means to move bits. This operation may be necessary in some form when the only nonlinear operation of each round is an s-box operation which uses only a small fraction of bits from one-to-one round segment. Rotation can ensure that all bits eventually become input of the non-linear operation, and thus have some nonlinear effect on the cipher data.
Khufu requires considerable time to generate its s-boxes, and is a complex block cipher. On the other hand, up to this point in time popular adoption of block ciphers historically has followed quick startup time and simplicity. To date it appears that no significant software packages appear to have embraced this block cipher. Khafre uses fixed s-boxes and is simpler than Khufu, but it appears it may use many large s-boxes and it is designed only to compute a 64-bit block cipher. Unfortunately, 64-bit block ciphers are generally insecure due to small block size. It appears that Khafre may use different s-boxes for succeeding rounds in order to avoid certain weaknesses which occur when an s-box is used in the same way to encrypt different cipher data. However, this significantly increases the amount of memory necessary to accommodate its s-boxes.
Due to the complexity of these ciphers, their security has not been evaluated thoroughly by many cryptanalysts. However, it is readily apparent that given a reasonable number of rounds or clock cycles computed, Khafre is not adequately secure.
Another more recent cipher has certain general properties of Khufu and Khafre and was published as a springboard for further investigation and research. This algorithm is called xe2x80x9cTest1xe2x80x9d (see, Bruce Schneier and Doug Whiting, xe2x80x9cFast Software Encryption: Designing Encryption Algorithms for Optimal Software Speed on the Intel Pentium Processorxe2x80x9d. Fast Software Encryptionxe2x80x94Fourth International Workshop, Leuven, Belgium, 1997, referred to herein as Schneier et al.). The algorithm was designed as part of a testbed of ideas about fast software rather than as a secure, simple, or practical block cipher.
The block cipher Test1 uses four registers of 32 bits, each of which contains a primary segment. In it each new primary round segment, R[t0], is a function of the last four previously calculated primary segments (R[txe2x88x921] thru R[txe2x88x924]). Its round equations vary significantly in various rounds to inject some irregularity into the algorithm. However, a typical round equation (Equation 3) of the cipher is as follows:                                                                         R                ⁡                                  [                  0                  ]                                            =                              xe2x80x83                            ⁢                              (                                                      (                                                                  R                        ⁡                                                  [                                                      -                            4                                                    ]                                                                    +                                              R                        ⁡                                                  [                                                      -                            1                                                    ]                                                                                      )                                    ⁢                                       less than  less than  less than                                     ⁢                                                            F-table                                        ⁡                                          [                      i                      ]                                                                      )                                                                                                        xe2x80x83                            ⁢                              xor                ⁢                                  xe2x80x83                                ⁢                                  (                                                            s                      ⁢                                              -                                            ⁢                                              box                        ⁡                                                  (                                                      LSB                            ⁡                                                          (                                                              R                                ⁡                                                                  [                                                                      -                                    2                                                                    ]                                                                                            )                                                                                )                                                                                      +                                          R                      ⁡                                              [                                                  -                          3                                                ]                                                                              )                                                                                        Eq        .                  xe2x80x83                ⁢        3            
In this round equation of this cipher the s-box receives input bits from the least significant bits (xe2x80x9clsbxe2x80x9d) of R[xe2x88x922]. The new primary segment R[0] reflects the linear combination of other values and the s-box output using generally non-commutative operators and using round-and-register dependent rotation. Nevertheless, use of non-commutative operators does not appear to be structured efficiently; further, the register size of 32 bits each is too small to gain significant cryptologic strength from use of non-commutative operators; and finally, the sbox is not optimized and may be random and such sbox may have, given all possible input differences, a minimum number of output bit-differences which is too small to provide adequate differential strength.
Of course, in this equation there are four primary round segments. As value R[xe2x88x924] is the old primary segment, the value of the new primary round segment R[0] is an invertible one-to-one function of the one-to-one round segment R[xe2x88x924] assuming all other inputs including other one-to-one round segments are constant. Although this property is true for this segment, when the property is repeated throughout the operative rounds, it makes possible the property for the cipher globally that its ordered n-bit inputs map one-to-one with its ordered n-bit outputs.
In practice, use of four registers to encrypt cipher data may be too many registers to achieve good security efficiently. Test1 also appears too complicated to be adopted as a mainstream block cipher. Further, Test1 uses only one s-box to conserve on-chip cache. It is not adequately clear that this approach is secure. Repetitive use of the same s-box in the same manner is usually insecure. While use of non-commutative operations does alleviate this concern somewhat, the registers are too small (only 32 bits) for the non-commutative operators to provide much additional strength. The cipher""s use of round-dependent rotation as specified in its F-table also alleviates this concern somewhat. Nevertheless, the round-dependent rotation schedule is fixed and known and hence may not provide adequate security given reuse of the same s-box in successive rounds if the s-box is known.
On the other hand, if the a s-box is generated in a key-dependent random manner prior to encryption as intended by Schneier et al., the bootup time of the cipher is increased substantially. Further, if such an s-box is generated randomly and hence not optimized to avoid potential flaws, there is also a potential risk of weak s-boxes.
By contrast, a symmetric encryptional method known as xe2x80x9cRC5xe2x80x9d (see R. Rivest, xe2x80x9cThe RC5 Encryption Algorithmxe2x80x9d Fast Software Encryptionxe2x80x94Second International Workshop, Leuven, Belgium, pages 86-96. Springer-Verlag, 1995) is based on a different paradigm. Unlike DES, Khufu and Khafre, RC5 uses no s-boxes. This fact eliminates the need to reserve large segments of on-chip cache in order to store the s-boxes. Thus, RC5 may be more practical to encrypt or decrypt standard packets of data, usually only 48 bytes each, received from the internet or other digitized phone networks. Such encryption or decryption may take place without having to allocate any time to transferring large s-boxes into on-chip cache.
RC5 is a Feistel block cipher which appears to be the first to use data-dependent rotation in a relatively efficient manner. A primary distinguishing feature of RC5 is the way in which, to calculate new one-to-one round segments, it rotates that segment in a variable, i.e., data-dependent, manner depending on particular bit-values in another one-to-one round segment. This data-dependent rotation is the operation which provides the cryptographic strength of RC5. It permits RC5 to eliminate s-boxes. S-boxes are nonlinear and may act in a complex data-dependent manner. For example, an s-box may affect some bits in a nonlinear manner based on the values of some other bits. If RC5 did not use rotation in a data-dependent manner, it appears it would need s-boxes or some other operation which acts in a data-dependent manner.
Referring herein to prior art FIG. 1, an algorithmic flow chart of the RC5 enciphering process is shown. A first block 10 contains plaintext input consisting of n bits at the start of the iterative enciphering process. Each plaintext input block is divided up into two primary segments, 12 (R0) and 14 (R1), each of which contain n/2 bits. For example, a 64-bit version of RC5 divides its input into two 32-bit block halves. Typically, in calculating a 64-bit version of RC5 each such block half or one-to-one primary round segment is to be contained in one 32-bit microprocessor register, which is the register size of most modern microprocessors.
Prior to beginning the iterative process, RC5 adds (blocks 16 and 18) one subkey value, K1 and K2, to each primary segment, R0 and R1. Each value of K1 and K2 can be the same or different. Similar to the one-to-one round segments, each such key value contains 1n/2 bits. Next, RC5 performs the first of many rounds of encryption. Each round of encryption computes new values of the primary segments R0 and R1. Each computation of the two primary segments is similar in form, even though it has different inputs and outputs and is stored in different registers.
To compute in the first half round the new primary segment R0, the following procedure is used. The half round uses xor (block 20) to combine the segments R0 and R1. Next, it extracts (block 24) a given number of bits (xe2x80x9cfxe2x80x9d bits) from the least significant bits of the right primary segment R1. For example, if f is 5 bits, it would extract the 5 least significant bits (xe2x80x9clsbxe2x80x9d) of R1 in order to provide one input used by the variable rotation.
The number of lsb in a one-to-one round segment (the lsb contain xe2x80x9cfxe2x80x9d bits) is that number which permits as many different rotations as are possible for a primary segment. For example, a 64-bit block has two primary segments of 32 bits each. The 32 possible rotations of these halves may be selected using f=5 bits, as 2{circumflex over ( )}5=32. Hence, for each potential block size there is an associated number of bits xe2x80x9cfxe2x80x9d which permits all potential rotations of the primary segments. Thus, the total number of different values of V extracted from the lsb of R1 may be as many 2{circumflex over ( )}f, or in this example 2{circumflex over ( )}5, possible values. It will be noted that the xe2x80x9cleast significant bitsxe2x80x9d which affect a rotation are crytographically speaking the most significant bits of each round.
Then, the xored values in the left primary segment R0 are rotated (block 26) by V, i.e., the value of the lsb. Finally, to this result is added (block 28) a subkey K3 for this half round. The resulting one-to-one primary round segment is the new value of R0 (block 30) from the first round.
This process is then repeated in the second half round to calculate the right primary segment R1 using the new value of R0. To compute in the second half round the new primary segment R1, the following procedure is used. The round uses xor (block 22) to combine the values of its primary segment R1 with that of the other primary segment R0. Next, it extracts the given number of bits (xe2x80x9cfxe2x80x9d bits) from the least significant bits of R0. Again, if f is 5 bits, it would extract (block 32) the 5 least significant bits (xe2x80x9clsbxe2x80x9d) of R0 in order to provide one input used by the variable rotation. Then, the xored values in the right segment R1 are rotated (block 34) by V, i.e., the value of the lsb. Finally, to this result is added (block 36) a subkey K4 for this half round. The resulting one-to-one primary round segment is the new value of R1 (block 38) from the first round.
Each round of RC5 is only part of a complete encryption of one plaintext block. Many rounds are generally necessary depending on block size. This number of rounds selected depends on block size and the users desire for security, but is typically greater than 8 and less than 64. After all rounds are completed the resulting ciphertext values of segments R0 (block 40) and R1 (block 42) are generated, which are then combined to generate ciphertext consisting of n bits (block 44).
Each round of RC5 in FIG. 1 may also be expressed as two equations, Equations 4 and 5 below, where each equation determines the bit-values of one primary segment and where each such segment corresponds to half an n-bit block of data. This description follows, where i is the index of the iterative round and where i is incremented by two between rounds (these equations ignore the initial addition of the subkeys K0, K1 to the plaintext):
R0=((R0 xor R1) less than  less than  less than LSB(R1))+Key[i]xe2x80x83xe2x80x83Eq. 4 
R1=((R1 xor R0) less than  less than  less than LSB(R0))+Key[i+1]xe2x80x83xe2x80x83Eq. 5 
Unlike DES, RC5 does not swap its one-to-one primary round segments between calculating each such segment. Consequently, RC5 requires fewer clock cycles for a given number of new segment values and also it is easier to understand.
Similar to DES, in RC5 each new value of a primary segment is a one-to-one function of its prior value given that the other one-to-one round segment and the subkeys are constant. Incidentally, in RC5 every round segment calculated in each round, with the possible exception of the value V which controls the data-dependent rotation, is a one-to-one round segment.
It will be noted that similar to the simplified structure of DES using no round segment swaps, the structure of RC5 ensures that the same operations affect each primary round segment: (1) the nonlinear operation of data-dependent rotation affects each primary segment R0 and R1 based on the small section bits of the other primary segment, (2) the linear combination of the two primary segments using xor affects each primary segments R0 and R1, and (3) modification by a new subkey value affects each primary segment R0 and R1.
Again, decryption is the inverse of encryption. All the same steps are repeated but in reverse order. Decryption uses ciphertext output as input and recovers the values of the plaintext inputs. The decryption round equations (Equations 6 and 7) of RC5 are simply the inverse of the encryption round equations:
R1=((R1xe2x88x92Key[i+]) greater than  greater than  greater than LSB(R0))xor R0xe2x80x83xe2x80x83Eq. 6 
R0=((R0xe2x88x92Key[i]) greater than  greater than  greater than LSB(R1))xor R1xe2x80x83xe2x80x83Eq. 7 
It should be apparent to one skilled in the art that the choice of which equations are used for encryption or decryption is a convention. Hence, it is possible to build a cryptographic system in which what is herein called the RC5 inverse equations are used for encryption, and what is herein called the RC5 encryption equations are used for decryption.
It is useful to define a quantitative measure called good bits which indicates the degree to which cumulative linear combination (i.e., the process of combining round segments in a linear manner to produce a new round segment) of round segments does or does not introduce good bits to affect a rotation. Good bits are those bits from cipher input which affect the small section of the segment which controls second round nonlinear activity but which do not affect the small section of the segment which controls first round nonlinear activity. Of course, it is useful to keep in mind that when this bit-tracing calculation of good bits is applied to decryption equations such input may be ciphertext which is ordinarily thought of cipher output, just as the output of the last round may be plaintext. Generally, the definition of good bits measures the number of small section bits which definitely control the nonlinear activities of each round which do not in general also control the nonlinear activities of the preceding round. For this reason, the number of good bits measures the inflow in each round of fresh or new data from linear diffusion which influence the nonlinear activities. When the number of good bits is at least half as large as the total use of small section bits to affect nonlinear activity in each round, or greater, then the block cipher has a property which may be called new small section data in successive rounds.
It is difficult to evaluate the good bits of two consecutive rounds of encryption of RC5 because during encryption all segment bits are rotated, hence it is uncertain rather than definite which input bits affect the nonlinear activity of the subsequent two rounds. Similarly, the use of addition or subtraction in encryption or decryption makes it uncertain rather than definite which bits affect which due to xe2x80x9ccarryxe2x80x9d bits in addition and subtraction which allow some input bits to affect more or less significant bits though often with a low probability.
In the case of ambiguity due to variable data-dependent rotation of all segments which are combined linearly, the total number of calculated good bits is zero since those segments should be excluded from the calculation of good bits. After first discarding any such bits from the determination of good bits, the calculation of good bits is based on whichever equation (encryption or decryption) generates a greater number of good bits. This greatest number of good bits provides a rough measure of the strength of the block cipher in the area of data-dependence and bit-diffusion.
Evaluation of good bits is done therefore using the decryption equations, eliminating any values which have been rotated by a variable operator, and converting all linear operators other than xor to xor. After making these changes it is possible with simplicity and consistency to trace which input bits of any n-bit round input definitely affect the first and second of two consecutive rounds in a nonlinear manner.
In the case of RC5, the input bits which affect its variable rotations in the second round due to linear diffusion are the same that do in the first round. These bits come from the lsb of the cipher input segments R0 and R1. Hence, there are no non-overlapping input bits which definitely control the small section nonlinear activity of the cipher in a second round but not in a first round, and the number of good bits in each round is zero. As the number of good bits (0) are much fewer than the number of bits which affect rotations in each round (2f), RC5 does not have the property of new small section data in successive rounds.
To understand a possible effect of inadequate new small section data in successive rounds, it is useful to understand the differential analysis of data-dependent rotation in RC5, and to examine a particular example. A typical differential attack on a block cipher relies on the fact that some bit inputs fail to affect other bit values in a block cipher. A good example of block cipher encryption may therefore illustrate in simplified manner how a typical differential attack might work.
Typically, differential attacks are effective because they use self-cancellation to extend the power of the differential method over multiple rounds. It turns out in most cases that there exist certain input differences between two related encryptions called differential characteristics which have a high probability of self-cancellation in the operative rounds of the block cipher, where after several rounds of encryption there is a high probability that the output bit-difference between the two encryptions equals the initial bit-difference.
For example, consider the following simple inputs into the RC5 block cipher in FIG. 1:
For Plaintext Input #1 let,
R0={0 0 0 0 0 0 0 0 . . . };R1={0 0 0 0 0 0 0 0 . . . }
For Plaintext Input #2 let,
R0xe2x80x2={0 0 0 0 1 0 0 0 . . . };R1xe2x80x2={0 0 0 0 1 0 0 0 . . . }
The difference between these registers is,
D0={0 0 0 0 1 0 0 0 . . . };D1={0 0 0 0 1 0 0 0 . . . }
In the above example, the only bit that is different in the two sets of one-to-one round segments is the fifth bit from the left. As the fifth bit in each segment is different, when xored together in the above RC5 equation (1) the difference in the inputs cancels out. Cryptanalysts are generally able to use such self-cancellation of input differences between two related encryptions to find differential characteristics that can with a certain probability pass through multiple rounds unaffected by the block cipher. It turns out that when assuming the bit input differences shown above the best probability of bits canceling out is seen in every third new register value (R0 in the 1 st round, R1 in the 2nd round, R0 in the 4th round, R1 in the fifth round, etc.).
It is possible to examine a simplified example which illustrates this type of differential analysis. First, it is useful to calculate a base case using RC5 in which nothing of cryptographic interest occurs. Using the plaintext input shown above where all bits equal 0, it is useful to assume that all subkey bit values also equal 0. These inputs result in potentially an infinite number of rounds of encryption in which all bits of each new one-to-one round segment equal 0. Of course, given these assumptions, the ciphertext output bits of RC5 also equal zero. This result is not surprising and reflects the simplified assumptions concerning subkey values.
Second, the interesting step in creating a useful illustration of the behavior of RC5 is to allow certain non-zero input bits. Using this approach, the new one-to-one round segments in succeeding rounds of this example based on an input or input-difference which has some non-zero bits illustrate the differential behavior of the cipher.
Referring herein to prior art FIG. 2 (wherein the blocks are numbered as in FIG. 1, with the numbers in the second round being designated with a prime), a simple example in which given input values where some bits are modified from the base case to non-zero bits, and the non-zero bits pass through two rounds of RC5 encryption with little or no effect upon the other bits is shown. As stated above, for simplicity and ease of explanation, all key values and most of the input values are equal to 0. This example is similar to the differential input difference shown above. Only the fifth bit of each register, i.e., each block half, has a value of 1. Note also that in this example, which is similar to a typical differential attack on a Feistel block cipher, every third primary segment or half round of RC5 contains bits in which any non-zero input bits have canceled out and all bits are equal to 0. In a differential attack on RC5 by a cryptanalyst, this self-cancellation property reduces the effort required to break the cipher.
It will be appreciated with RC5 encryption, that even with an infinite number of rounds a particular bit may not be affected. With these assumptions, it turns out that the fifth input bit in these registers with a value of 1 cannot ever affect a rotation. In other words, an infinite number of rounds are required until the input bit affects a rotation.
Of course, this example is only possible due to weak subkey values. All values of the subkeys equal zero. In this example, the weak rotations which permitted this result to come about depend primarily on certain subkey values; and the rotations in the example shown above are affected by a total of only 8 plaintext bits. In FIG. 2, the data values which affect the rotations are the initial least significant 4 bits of each plaintext block half.
It is worth noting that this block cipher may iterate through potentially a large number of rounds, and yet the output may depend primarily on only eight plaintext bits and on those subkeys which influence the one-to-one round segments associated with those plaintext bits. This suggests that the block cipher violates a requirement of a secure block cipher in that every output bit depends on every bit of plaintext input and on every bit of key input.
The primary weakness shown in this example of RC5 is that, assuming worst case variable data dependent rotations, the variable cipher data circulate in such a manner such that in certain rounds (where in general one round is a number of steps large enough that this number of data-dependent rotations is at least as great as the number of primary round segments in the block cipher) there exists a small set of potentially stagnant or isolated stationary variable bits in specified bit-positions which control the number of bits of all data-dependent rotations (xe2x80x9cspecified isolated bitsxe2x80x9d) where by definition a) only that set of specified isolated bits in the specified bit-positions can control the data-dependent rotations, and b) only that set of specified isolated bits in the specified bit-positions can affect the values of the specified isolated bits in the same specified bit-positions. By definition, the number of specified isolated bits is the smallest number possible assuming any possible data-dependent rotations. This means, assuming that those data-dependent rotations occur, there is a minimum number of specified isolated bits where only those bits can control the degree of data-dependent rotations in the block cipher, and only those specified isolated bits can affect their own values.
In the case of RC5-32 (i.e., using the example shown above and in FIG. 2 which has a 32-bit block size and two 16-bit halves), in one round there are 8 specified isolated bits, which are the least significant 4-bits of each of the two round segments of the block halves, where in that round only the 8 specified isolated bits affect data-dependent rotations, and assuming a data-dependent rotation of zero bits the specified isolated bits are affected only by the specified isolated bits in that round. As previously stated, this number of specified isolated bits is invariant as the number of rounds increases. In other words, given an infinite number of rounds, it is still theoretically possible that in RC5 an input bit might not affect a data-dependent rotation. Further, the number of specified isolated bits is a small fraction of the number of bits in the n-bit variable cipher data block (in this example, the 8 specified isolated bits are only 25 percent of the total of 32-bits in the total data block).
The weakness of RC5-32 can be seen using Equations 4 and 5. The specified isolated bits are in the least significant 4 bits in bit-positions 0 through 3 of each of the block halves R0 and R1. Only bits in these positions can affect the data-dependent rotations. The xor of the block halves combines the bit-positions 0 through 3 in each of the block halves, to produce a result where its least significant 4 bits in bit-positions 0 through 3 depend only on the specified isolated bits. Assume data-dependent rotations of zero bits. If so, the new bit-values of the 4 least significant bits of R0 and R1, in the positions of the specified isolated bits, depend only on values of the specified isolated bits. Assuming these data-dependent rotations are always zero, even given an infinite number of rounds there is no way that other bits which are not specified isolated bits can influence the specified isolated bits, nor is there any way that the other bits can influence value V, which determines the data-dependent rotations.
The existence of a small number of specified isolated bits in a round which cannot be influenced by other bits subject to certain assumptions about variable rotations is a sign that a cipher round or rounds are inadequately secure. The question of whether there exists a subset of the n-bit data block of a block cipher which satisfies this cryptographic property of being specified isolated bits is a logical question applicable to a specific round and also to consecutive rounds of each block cipher.
In analyzing the RC5 equations using block sizes of 64-bits and 128-bits, there are specified isolated bits where the total number of such bits is similarly low. The total numbers of specified isolated bits is only 10 bits out of 64, and 12 bits out of 128 respectively for these block sizes.
Further, when analyzing RC5 by replacing all use of addition or subtraction with xor for analytical simplicity (RC5 after this substitution of operators is roughly as strong analytically), it is clear that other more complicated subkey schedules can result in larger possible sets of specified isolated bits where those sets of specified isolated bits are still a small number of bits, i.e., are a subset of the possible maximum, and often are 50 percent or less of the possible maximum number of variable bits in the cipher data block.
This potential problem in which the data-dependent rotations of RC5 depend after many rounds primarily on a small number of bits of the subkey and on a small number of input bits appears to be related to having inadequate small section data in successive rounds. In particular, in RC5 there seems to be a correlation or coincidence of weakness. In the instances in which RC5 is weak differentially, it is also weak in diffusing input bits and any changes in input bits. Calculating the number of bits of new small section data in successive rounds in fact gives us a crude way of estimating the degree of linear diffusion of input differences in one-to-one round segments when the variable data-dependent rotation is otherwise unable to provide adequate diffusion. It appears that this coincidence of weakness reduces the potential diffusive and differential strength of data-dependent rotation significantly.
Cipher attacks which limit their analysis of RC5 to plaintext inputs which prevent rotations from occurring in the initial rounds are said to take advantage of weak subkeys. All subkeys of ciphers depending on data-dependent rotation have some plaintext inputs for which this is true, though it is easier to use this type of attack when the rotations depend on as few plaintext inputs as possible. Similarly, cipher attacks which limit their analysis of RC5 to input values which provide rotations which cancel out some input differences with a high probability are said to take advantage of differentially weak subkeys. It may be that all subkeys of ciphers using data-dependent rotations have plaintext inputs for which this is true, though it is easier to use this type of attack when such rotations depend on as few plaintext inputs as possible.
The example above in FIG. 2 in which all subkeys equal 0 illustrates both weak subkeys and differentially weak subkeys given inputs of 0 in the least significant 4 bits of both plaintext inputs.
While most subkeys in RC5 do not provide results as weak as the example above, there are in fact a multitude of potential examples of weak subkeys. Increasingly, it seems that the most effective attacks on RC5 take advantage of such weak subkeys. It would seem preferred then not to use RC5 without a way of screening out either weak subkeys, or at a minimum differentially weak subkeys. However, as a practical matter the generation of subkeys in RC5 is already slow and to additionally screen out or eliminate weak subkey values would be time consuming and complex.
The most significant recent cryptanalytic study of RC5 was written by Knudsen and Meier (Lars R. Knudsen and Willi Meier, Improved Differential Attacks on RC5, Advances in Cryptologyxe2x80x94Crypto ""96, pages 216-228. Springer-Verlag, 1996). This study fine-tuned a differential attack first discussed by Kaliski and Yin (B. Kaliski and Y. L. Yin, On Differential and Linear Analysis of the RC5 Encryption Algorithm, Advances in Cryptologyxe2x80x94Crypto ""95, pages 171-184. Springer-Verlag, 1995).
While the study of Kaliski and Yin suggested that sixteen (16) rounds of RC5 might be sufficient for a 128-bit RC5 block cipher to resist differential attack, the attacks by Knudsen and Meier obtain better results by detecting and taking advantage of weak subkeys. As a result, they are potentially able to penetrate many more rounds of RC5. Due to the increasing progress that is being made in such attacks, the security of RC5 is uncertain. It is clear that RC5 has some weaknesses which may make it too insecure for widespread use.
In order to block this type of attack it would be necessary to increase the work required to detect and to take advantage of weak subkeys. It appears that the reason such weak subkey attacks penetrate many more rounds than the more general attack by Kaliski and Yin is that the data-dependent rotations of RC5 may depend primarily on only some subkey values and some cipher input bits.
An unrelated potential weakness of RC5 is that it has a complex and somewhat slow key expansion method. This method requires roughly nine operations per subkey, or eighteen operations per round, in order to expand RC5xe2x80x2s input key. Efficient encryption and decryption of standard 48-byte digital network packets requires quick key expansion.
It should be noted it is not accidental that the key expansion method in RC5 is somewhat slow. In particular, RC5 uses a complex nonlinear method using key data-dependent rotations to expand its key.
The use in RC5 of a complex slow means of generating the key is consistent with the perspective of cipher designers that the key expansion method xe2x80x9cshould maximize avalanche in the subkeys and avoid linear key schedulesxe2x80x9d (see xe2x80x98Key Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DESxe2x80x99, by John Kelsey, Bruce Schneier, David Wagner, in Advances in Cryptology, Crypto ""96, pp. 248-249). The RC5 key expansion method is nonlinear and maximizes avalanche and as a result it is considered secure; and use in RC5 or other block ciphers of an alternative linear key expansion would be perceived by cryptographers as weak.
The above-discussed and other drawbacks and deficiencies of the prior art are overcome or alleviated by the improved block cipher method of the present invention, wherein it is an object of the invention to provide cryptographic systems and methods which are secure.
It is another object of the invention to provide a cryptographic system and method which uses data-dependent rotation with a novel iterative calculation which is robust. The robust quality of encryption using this method resists attacks by sophisticated algorithms which detect and take advantage of weak subkeys to determine the keys of the cryptographic system.
It is another object to provide a novel mechanism and method for quick key expansion, particularly for encryption rounds with data-dependent rotation, which decreases the time required to prepare a block cipher to encrypt or decrypt digital packets of bytes.
It is still another object of the invention to provide a cryptographic system and method of the above character which uses minimal numbers of s-boxes with a novel iterative calculation where the block cipher does not require an excessive startup time, yet is simple, secure and efficient for bulk encryption. The block cipher of the present invention uses no more on-chip cache than necessary, and uses its s-boxes in a secure manner.
It is yet another object to provide a novel mechanism and method for complex key expansion, which uses a minimum amount of time to prepare a block cipher to encrypt or decrypt a large file and which nevertheless ensures that the subkeys generated by the method reflect every bit of the key in a complex uncorrelated manner.
The foregoing objects, and others, are accomplished by the data encryption system for encrypting an n-bit block of input in a plurality of rounds of the present invention, where n is preferably 128 bits or more. The data encryption system includes a computing unit for the execution of each round; memory for storing and loading segments; a bit-moving function capable of rotating bits (or of otherwise moving bits into different positions) of one-to-one round segments by predetermined numbers of bits; a linear combination function which provides new round segments using a round operator generally from a first algebraic group to combine two different round segments; and a nonlinear function which affects a round segment based on a value which depends on bits from another round segment, where both round segments are different round segments from the same one-to-one round segment set. A round operator is a mathematical operation capable of being carried out in a microprocessor in computing an operative round, such as addition, subtraction, bitwise exclusive-or, or rotation.
Both embodiments of the present invention are block ciphers with cipher data blocks preferably of at least 128 bits, which are either Feistel ciphers or near-Feistal ciphers. The Feistal ciphers divide the data block up into no more than two block halves of SZ bits, wherein the halves are primary round segments and SZ is a value as small as 64 and as large as 128. The near-Feistel block ciphers divide the data block into no more than two large segments, each containing 64 or 128 bits, and a third typically small primary round segment typically not to exceed 20 bits. In practice, this means that both embodiments of the current invention use mathematical operations computable on a microprocessor which act on either a 64-bit or a 128-bit segment of cipher data.
This use of the Feistel approach with no more than two large data segments is a critical aspect of the invented block cipher as it permits the block cipher to be efficient, secure, and also practical in a range of modern processors. Embodiments of this Feistel or near-Feistel approach generally modify each of the primary round segments in each round of calculation in the same way, typically using operations which modify all the bits of the large primary round segments in single linear operations. While the present invention is not restricted to use of a Feistel or near-Feistel approach, this approach is generally beneficial to the security of the cipher.
On the other hand, certain operations such as 64-bit data-dependent rotations are not yet implemented with maximum efficiency on 32-bit processors such as Pentium MMX chips. This means that block ciphers with block sizes in excess of 64-bits and which use data-dependent rotations may end up using from 4 to 8 data segments of 32-bits each.
For other block ciphers, especially those using sboxes implemented using MMX instructions, there do not appear to be any special efficiency constraints encountered as a result of using only two large data segments of 64-bits or larger. Although it is possible to implement a block cipher of the present invention which uses sboxes and which has more than two large data segments of 64-bits or greater (and may use between 2 and 4 such large data segments), it is strongly preferred to use only two such large primary round segments.
Despite the fact that efficiency constraints may compel use of up to 8 primary round segments in a block cipher using data-dependent rotation, it is preferred for reasons of maximizing security and efficiency that no more than 4 primary round segments are used. It is also preferable for reasons of maximizing security and efficiency that the block size is at least 128 bits, that such block size be predetermined (rather than of variable or perhaps text-dependent size), and related to these points, it is preferred that the minimum size of the round segments rotated by the a data-dependent variable rotation function is at least 32 bits.
While it is not obvious how best to achieve various mathematical properties in a Feistel block cipher or even which properties are most important, designers of secure block ciphers continue to focus on inventing new Feistel block ciphers. Good design of Feistel block ciphers is difficult because the structure is so simple that designers cannot randomly insert into a cipher xe2x80x9ceverything but the kitchen sinkxe2x80x9d and hope that something encrypts the cipher data in a secure manner. The simplicity of Feistel block ciphers permits purest expression of good encryption methods. Use of a Feistel block cipher structure by itself does not promote secure encryption, but the structure is synergistic with good encryption methods. Good Feistel ciphers are not randomly designed, but have regularly repeating rounds in which identical operations occur in a similar manner.
Such Feistel block ciphers have the best record of security and popularity in the field of encryption. DES is an aging, but still viable encryption standard which is a Feistel block cipher. xe2x80x9cRC5xe2x80x9d is a new paradigm using data-dependent rotations in a Feistel block cipher. As a further example of a secure new encryption standard, one embodiment of this invention uses relatively non-commutative operators for sbox output combination and for linear diffusion in a Feistel or near-Feistel block cipher.
In one embodiment of the present invention, the nonlinear function is a variable rotation function executable on the computing unit which generally rotates a one-to-one round segment by a value which depends on a preselected number of bits from a preselected location of a different one-to-one round segment from the same one-to-one round segment set.
In another embodiment of the present invention, the nonlinear function is an s-box and the system generally includes a s-box linear combination function which uses a round operator generally from a second algebraic group executable on the computing unit which combines a one-to-one round segment with the output of an s-box lookup of a value which depends on a preselected number of bits from a preselected location in a different one-to-one round segment from the same one-to-one round segment set, wherein the first algebraic group is preferably non-commutative with the second algebraic group.
Generally, all embodiments of the system of the present invention have a subkey combining function in each round which provides new round segments by combining a round segment typically linearly with a subkey segment, where the number of times the subkey function is used in the rounds of the cipher is roughly equal to the number of times in such rounds the nonlinear function is used, or in any case is at least half of the number of times in such rounds the nonlinear function is used. Qualified operative rounds of a binary block cipher refer to such rounds of the block cipher which exhibit some particular, generally good, cryptographic properties.
The key expansion method applicable to data-dependent ciphers of the present invention detailed herein provides a rapid subkey generation method which permits control of the differences between subkeys using fixed table values and given well-chosen fixed table values could help to limit problems related to differentially weak subkeys, and to weak subkeys in general.
The above-discussed and other features and advantages of the present invention will be appreciated and understood by those skilled in the art from the following detailed description and drawings.